// 动态规划法
// 通过构建一个二维数组来记录公共子串的长度，从而找出最长公共子串。

// 子串（Substring）：必须是连续的字符。
// 子序列（Subsequence）：可以不连续，但顺序必须保持一致。


function longestCommonSubstring(str1, str2) {
  const len1 = str1.length;
  const len2 = str2.length;
  let maxLength = 0;
  let endIndex = 0;

  // 创建一个二维数组来记录公共子串的长度
  const dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0));

  // 动态规划计算公共子串的长度
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i - 1;
        }
      } else {
        dp[i][j] = 0;
      }
    }
  }

  // 根据最大长度和结束索引提取最长公共子串
  return str1.slice(endIndex - maxLength + 1, endIndex + 1);
}

// 示例使用
const str11 = "abcdef";
const str22 = "abxyzdef";
const result0 = longestCommonSubstring(str11, str22);
console.log(result0);     